Still union find, it is easy to identify, but there is little twist, initially I thought of sorting the edges, so we can union type 3 first, but this takes n log n time because sorting is bound by that, if we traversal twice the edges, still we only take just n time, so it would actually beat the way I implemented at begining. other than this, this question uses two union find data structure but everthing should be just the same.
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
// still union find
// we can remove edge if when we trying to connect the nodes are already connected
UnionFind alice = new UnionFind(n);
UnionFind bob = new UnionFind(n);
int res = 0;
// do union for type 3 first
for(int[] edge : edges){
if(edge[0] == 3){
int a = edge[1];
int b = edge[2];
res += (alice.union(a,b) | bob.union(a,b));
}
}
for(int[] edge : edges){
int type = edge[0];
int a = edge[1];
int b = edge[2];
if(type == 1){
res += alice.union(a,b);
}else if(type == 2){
res += bob.union(a,b);
}
}
if(alice.isValid() && bob.isValid()){
return edges.length - res;
}else{
return -1;
}
}
public class UnionFind {
int[] parent;
int[] size;
int n;
public UnionFind(int n){
parent = new int[n + 1];
size = new int[n + 1];
for(int i = 0; i <= n; i ++){
parent[i] = i;
size[i] = 1;
}
this.n = n;
}
public int find(int a){
if(parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
public int union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(size[pa] > size[pb]){
// join b into a
parent[pb] = a;
size[pa] += size[pb];
}else{
parent[pa] = b;
size[pb] += size[pa];
}
n --;
return 1;
}
public boolean isValid(){
return n == 1;
}
}
}